# 初始化种群
"""
backpack.txt 文件说明
6                          # 物品数量
1  2  3  4  5  6...        # 编号
23 12 43 23 12 34 ...      # 重量
5  4  1  3  7  3 ...       # 价值
在背包重量为N的情况下，求解携带价值最多的解组合

编码解 x = {0,1,1,0,1} 代表在1的位置取值为否，即不携带1号物品 在2号位为1表示携带2号物品

"""
import random
import time
import string

# 物品数量，即基因的长度
N = 0
# 种群规模
SCALE = 20
VALUE = []
WEIGHT = []
# 背包一共能装的重量
LIMIT = 90
SIZE = 6
# 种群
POPU = []
# 每个基因的变异概率 （1-100）
CHANCE = 20


# 读数据文件
def init():
    file = open("./backpack.txt", "r")
    global N, WEIGHT, VALUE
    N = file.readline()
    file.readline()
    WEIGHT = list(map(int, file.readline().split()))
    VALUE = list(map(int, file.readline().split()))

# 创建一个适应度非0的基因
def getOneGene():
    gene = ''
    for j in range(0, int(N)):
        gene = gene + str(random.randint(0, 1))
        # 如果适应度为0直接重新生成
    while Fitness(gene) == 0:
        gene = ''
        for j in range(0, int(N)):
            gene = gene + str(random.randint(0, 1))
    return gene

# 初始化种群
def initiate():
    global POPU
    POPU = []
    for i in range(0,SCALE):
        gene = getOneGene()
        POPU.append(gene)
        gene = ''
# 计算总重量
def calculateWeight(gene):
    weight = 0
    for index in range(len(gene)):
      if gene[index] == '1':
        weight = weight + WEIGHT[index]
    return weight


# 计算总价值
def calculateValue(gene):
    value = 0
    for index in range(len(gene)):
        if gene[index] == '1':
         value = value + VALUE[index]
    return value


# 适应度函数 重量越轻 价值越高
def Fitness(gene):
    fitness = 0
    # 如果重量大于最大值 适应度为0
    if calculateWeight(gene) > LIMIT:
        fitness = 0
    else:
    # 如果重量没有超过额度，那么价值就是适应度
        fitness = calculateValue(gene)
    return fitness

# 选择算子
def select():
    global POPU
    global SCALE
    # 总适应度
    allFit = 0
    fits = {}
    for i,item in enumerate(POPU):
        fitness = Fitness(item)
        allFit = allFit + fitness
        fits[i] = [fitness,allFit]
        # 淘汰适应度为0的
        if fitness == 0:
            POPU.pop(i)
            # 如果删除了一个为0的则生成一个新的基因
            # TODO 这里也可以繁殖一个新的基因出来
            POPU.append(getOneGene())
    # 轮盘赌 循环规模次数的计算 每次产生一个随机数[0-总适应度) 若满足  fits[i][1] - fits[i][0] <= 该随机数 < fits[i][1]
    newPOPU = []
    oldPOPU = POPU
    for i in range(0, len(oldPOPU)):
        seek = random.randint(0, allFit)
        for j in range(0,len(oldPOPU)):
            if fits[j][1] - fits[j][0] <= seek < fits[j][1]:
                newPOPU.append(POPU[j])
    if len(newPOPU) < len(POPU):
        ca = len(POPU) - len(newPOPU)
        for k in range(0,ca):
            newPOPU.append(intersect(POPU[len(POPU)-1],POPU[0]))
            SCALE = SCALE + 1
    POPU = newPOPU
    return 0

# 变异算子
def mutatio():
    global CHANCE
    global POPU
    for i in range(0, len(POPU)):
        seek = random.randint(0, 100)
        if seek < CHANCE:
            # 变异位
            index = random.randint(0,SIZE-1)
            POPU[i] = replace_char(POPU[i],index)

def replace_char(old_string, index):
    old_string = str(old_string)
    flag = ''
    if old_string[index] == '1':
        flag = '0'
    else:
        flag = '1'
    new_string = old_string[:index] + flag + old_string[index+1:]
    return new_string
# 交叉算子 随机产生交叉点 两个基因产生新的基因
def intersect(gene1,gene2):
    seek = random.randint(1, SIZE - 1)
    gene1_f = gene1[0:seek]
    gene2_e = gene2[seek:len(gene1)]

    gene1 = gene1_f + gene2_e
    return gene1
    # print(gene1_e)
if __name__ == '__main__':
    # 记录开始时间
    start_time = time.time()

    init()
    initiate()
    print(POPU)
    for i in range(0,200000):
        if select() == -1:
            break
        mutatio()
        # intersect('101010','011001')
    valus = []
    for i in POPU:
        valus.append(calculateValue(i))
    print(valus)
    print(POPU)


    # 记录结束时间
    end_time = time.time()

    # 计算运行时间
    run_time = end_time - start_time
    print('程序共执行{}秒'.format(run_time))

